题目

题目：请实现一个函数，把字符串中的每个空格替换成"%20"。

例如输入 “We are happy.”，则输出 “We%20are%20happy.”。

解法1[Java]：从后向前扫描并替换空格

public class Solution {
    public String replaceSpace(StringBuffer str) {
        int p1 = str.length() - 1;
        for (int i = 0; i <= p1; i++)
            if (str.charAt(i) == ' ')
                str.append("  ");

        int p2 = str.length() - 1;
        while (p1 >= 0 && p2 > p1) { //在完成最后一个空格的替换之后，p1等于p2
            char c = str.charAt(p1--);
            if (c == ' ') {
                str.setCharAt(p2--, '0');
                str.setCharAt(p2--, '2');
                str.setCharAt(p2--, '%');
            } else {
                str.setCharAt(p2--, c);
            }
        }
        return str.toString();
    }
}

这个问题要求贴近底层的思考方式，直接对字符进行操作。

如果从前向后扫描空格然后把空格替换成 %20，那么就会导致这个空格之后字符需要整体向后移动，如果采用这种方式，那么时间复杂度会变成 $O(n^2)$。

从后向前扫描替换的话，先扫描一遍字符串，根据空格的数量在字符串的末尾先补充足够的空格，每遇到一个空格，就在末尾补充两个空格，这样扫描一遍下来，替换之后的字符串的总长度就会确定下来。

相关链接

1. StringBuffer - Java Docs